POI2013 Tower Defense game

POI2013 Tower Defense game

题目大意：

(来自BZOJ Jiry_2的翻译)

有一天XYW在4399上玩一个塔防游戏：

有n座城市由m条双向道路连接。XYW可以在城市中建防御塔，每一座防御塔可以保护它所在的城市以及和这座城市有道路直接连接的城市。

由于XYW比较蠢萌，他建了n座塔保卫了所有城市。

突然XYW的男人看到了他的电脑屏幕：我只要用k座塔就可以了。（保证存在仅用k座塔就可以保卫所有城市的情况）

XYW不想被他的男人嘲笑，于是他就开始想如何用k座塔保护所有城市。

由于XYW比较蠢萌，他想不出来。

于是他更改了游戏规则：每一座塔可以保护和它所在城市最短距离在两条道路以内的所有城市。

请你给他一种用k座以内加强过的塔保护所有城市的方案。

题解:

每次找一个没有被覆盖的点，在该城市上建塔，并覆盖。则一定可以得到一个有效的解。

证明也比较简单：题目保证用老版的塔可以得到解，那么这意味着在原版的方案中，每一个城市相邻至少有一个塔。那么我们把塔建在当前节点，既能够起到原塔的作用，又可以覆盖更大的范围，显然更优。

Code:

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=(int)5e5+1,M=(int)2e6+1;
int n,m,k,head[N],tot_edge;
struct Edge{
	int to,nxt;
}edge[M];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
bool used[N],is_build[N];
struct Stack{
	int num[N],tp;
	Stack(){
		tp=0;
	}
	void push(int v){
		num[tp++]=v;
	}
	void pop(){
		--tp;
	}
	int top(){
		return num[tp-1];
	}
	bool empty(){
		return tp==0;
	}
}stk;
int main(){
	Rd(n),Rd(m),Rd(k);
	for(int i=1;i<=n;i++)head[i]=-1;
	for(int i=1,a,b;i<=m;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);
	}
	for(int i=1;i<=n;i++)stk.push(i);
	int res=0;
	while(!stk.empty()){
		int p=stk.top();stk.pop();
		if(used[p])continue;
		is_build[p]=used[p]=true;
		res++;
		for(int i=head[p];~i;i=edge[i].nxt){
			int to=edge[i].to;
			used[to]=true;
			for(int j=head[to];~j;j=edge[j].nxt){
				int nxt=edge[j].to;
				used[nxt]=true;
			}
		}
	}
	printf("%d\n",res);
	for(int i=1;i<=n;i++)
		if(is_build[i])printf("%d ",i);
	return 0;
}